##########程序测试#######

###1、生成20个0-100的随机数字，并统计出现次数
#导入标准库
# s=[1,3,5,1,4,22,3,4,2]
# print(f's:{s}')
# s.sort()  #对原列表排序，不查重
# print(s)

# import random
# alist=[random.randint(0,100) for i in range(10)]
# print(alist)
# alist.sort()
# print(f'alist:{alist}')
# for i in alist:

# import random
# list=[]
# for i in range(1000):
#     m=random.randint(1,100)
#     print(i,':',m)
#     list.append(m)
# print(list)

###2、切片操作

# for i in range(x):
#     num=int(input("输入列表元素"))
#     nums.append(num)

#x=int(input("输入列表元素个数"))
# print("请输入元素")
# nums=[int(input()) for i in range(x)]
# num=input().split()
# nums=[int(i) for i in num]
# print(nums)
# a=int(input("请输入切片范围："))
# b=int(input())

# my_dict = {"John": 1, "Michael": 2, "Shawn": 3}
#
# list_of_key = list(my_dict.keys())
# list_of_value = list(my_dict.values())
#
# position = list_of_value.index(1)
# print(list_of_key[position])
#
# position = list_of_value.index(2)
# # print(list_of_key[position])
# while(1):
#     flag=0
#     my_dict={'姓名':'name','年龄':'age','成绩':'score'}
#     num=input("输入要查找的键：")
#     for key,value in my_dict.items():
#         if num==key:
#             print(value)
#             flag=1
#     if flag==0:
#         print("您输入的键不存在！")

#####3、前10个数升序，后10个数降序

##先切片后排序，最后拼接

# import random
# nums=[random.randint(0,100) for i in range(20)]
# print(nums)
# a=nums[0:10]
# b=nums[10:20]
# print(nums)
# print(a)
# print(b)
# a.sort()
# print(a)
# b.sort()
# print(b)
# b.reverse()
# print(b)
# nums=a+b
# print("nums=",nums)

# if {3:5}:
#     print('hhh')
#
# for x,(f,s) in enumerate(zip((1,2,3),[4,5])):
#     print(f, end =',')
# for i in range(3):
#     print(i,end=',')吧

# year=int(input("请输入年份："))
# if(year%4==0 and year%100!=0)or(year%400==0):
#     print("是闰年！")
# else:
#     print("不是闰年！")

# import random
# nums=[]
# for i in range(50):
#     nums.append(random.randint(1,100))
# print(nums)
# for i in range(49,-1,-1):
#     # print("i",i)
#     # print("nums[i]",nums[i])
#     if nums[i]%2!=0:
#         #print("nums[i]",nums[i])
#         nums.remove(nums[i])
#         #print(nums[i])
#         print(nums)
# print("删除奇数后nums=",nums)


# import random
# s=[random.randint(1,50) for i in range(20)]
# print("before s:",s)
# a=s[::2]
# print("before a:",a)
# a.sort(reverse=True)
# print("after a:",a)
# s[::2]=a
# print("s:",s)


###计算y值

# x=int(input("请输入x:"))
# if x<0:
#     y=0
# elif 0<=x<5:
#     y=x
# elif 5<=x<=10:
#     y=3*x-5
# else:
#     y=1
# print(y)



# ###eval(x)  将字符串x转化为对应类型（去除引号，自动变为引号内类型）
# a="{1:'a',2:'b',3:'c'}"
# print(type(a))
# b=eval(a)
# print(type(b))

# while(1):
#     a=input("请输入:")
#     print('a:',type(a))
#     b=eval(a)
#     print('b:',type(b))





# a=eval(input('please input a list:'))
# start,end=eval(input('please input the start position and the end position:'))
# print(a[start:end+1])
#
#

# import heapq
# import copy
# import re
# import datetime
#
# BLOCK = []
# GOAL = []
# direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
# OPEN = []
# SUM_NODE_NUM = 0
#
#
# class State(object):
#     def __init__(self, gn=0, hn=0, state=None, hash_value=None, par=None):
#         self.gn = gn
#         self.hn = hn
#         self.fn = self.gn + self.hn
#         self.child = []
#         self.par = par
#         self.state = state
#         self.hash_value = hash_value
#
#     def __lt__(self, other):
#         return self.fn < other.fn
#
#     def __eq__(self, other):
#         return self.hash_value == other.hash_value
#
#     def __ne__(self, other):
#         return not self.__eq__(other)
#
#
# def manhattan_dis(cur_node, end_node):
#     cur_state = cur_node.state
#     end_state = end_node.state
#     dist = 0
#     N = len(cur_state)
#     for i in range(N):
#         for j in range(N):
#             if cur_state[i][j] == end_state[i][j]:
#                 continue
#             num = cur_state[i][j]
#             if num == 0:
#                 x = N - 1
#                 y = N - 1
#             else:
#                 x = num / N
#                 y = num - N * x - 1
#             dist += (abs(x - i) + abs(y - j))
#     return dist
#
#
# def test_fn(cur_node, end_node):
#     return 0
#
#
# def generate_child(cur_node, end_node, hash_set, open_table, dis_fn):
#     if cur_node == end_node:
#         heapq.heappush(open_table, end_node)
#         return
#     num = len(cur_node.state)
#     for i in range(0, num):
#         for j in range(0, num):
#             if cur_node.state[i][j] != 0:
#                 continue
#             for d in direction:
#                 x = i + d[0]
#                 y = j + d[1]
#                 if x < 0 or x >= num or y < 0 or y >= num:
#                     continue
#                 global SUM_NODE_NUM
#                 SUM_NODE_NUM += 1
#                 state = copy.deepcopy(cur_node.state)
#                 state[i][j], state[x][y] = state[x][y], state[i][j]
#                 h = hash(str(state))
#                 if h in hash_set:
#                     continue
#                 hash_set.add(h)
#                 gn = cur_node.gn + 1
#                 hn = dis_fn(cur_node, end_node)
#                 node = State(gn, hn, state, h, cur_node)
#                 cur_node.child.append(node)
#                 heapq.heappush(open_table, node)
#
#
# def print_path(node):
#     num = node.gn
#
#     def show_block(block):
#         print("---------------")
#         for b in block:
#             print(b)
#
#     stack = []
#     while node.par is not None:
#         stack.append(node.state)
#         node = node.par
#     stack.append(node.state)
#     while len(stack) != 0:
#         t = stack.pop()
#         show_block(t)
#     return num
#
#
# def A_start(start, end, distance_fn, generate_child_fn, time_limit=10):
#     root = State(0, 0, start, hash(str(BLOCK)), None)
#     end_state = State(0, 0, end, hash(str(GOAL)), None)
#     if root == end_state:
#         print("start == end !")
#     OPEN.append(root)
#     heapq.heapify(OPEN)
#     node_hash_set = set()
#     node_hash_set.add(root.hash_value)
#     start_time = datetime.datetime.now()
#     while len(OPEN) != 0:
#         top = heapq.heappop(OPEN)
#         if top == end_state:
#             return print_path(top)
#         generate_child_fn(cur_node=top, end_node=end_state, hash_set=node_hash_set,
#                           open_table=OPEN, dis_fn=distance_fn)
#         cur_time = datetime.datetime.now()
#         if (cur_time - start_time).seconds > time_limit:
#             print("Time running out, break !")
#             print("Number of nodes:", SUM_NODE_NUM)
#             return -1
#     print("No road !")
#     return -1
#
#
# def read_block(block, line, N):
#     pattern = re.compile(r'\d+')
#     res = re.findall(pattern, line)
#     t = 0
#     tmp = []
#     for i in res:
#         t += 1
#         tmp.append(int(i))
#         if t == N:
#             t = 0
#             block.append(tmp)
#             tmp = []
#
#
# if __name__ == '__main__':
#     try:
#         file = open('infile.txt', "r")
#     except IOError:
#         print("can not open file infile.txt !")
#         exit(1)
#     f = open("infile.txt")
#     NUMBER = int(f.readline()[-2])
#     n = 1
#     for i in range(NUMBER):
#         l = []
#         for j in range(NUMBER):
#             l.append(n)
#             n += 1
#         GOAL.append(l)
#     GOAL[NUMBER - 1][NUMBER - 1] = 0
#     for line in f:
#         OPEN = []
#         BLOCK = []
#         read_block(BLOCK, line, NUMBER)
#         SUM_NODE_NUM = 0
#         start_t = datetime.datetime.now()
#         length = A_start(BLOCK, GOAL, manhattan_dis, generate_child, time_limit=10)
#         end_t = datetime.datetime.now()
#         if length != -1:
#             print("length =", length)
#             print("time =", (end_t - start_t).total_seconds(), "s")
#             print("Nodes =", SUM_NODE_NUM)666666666666666666
#


# import heapq
# import time
#
#
# class Node:
#     def __init__(self, state, parent=None, cost=0, heuristic=0):
#         self.state = state
#         self.parent = parent
#         self.cost = cost
#         self.heuristic = heuristic
#
#     def __lt__(self, other):
#         return self.cost + self.heuristic < other.cost + other.heuristic
#
#
# def h1(state, goal_state):
#     distance = 0
#     for i in range(3):
#         for j in range(3):
#             if state[i][j] != goal_state[i][j] and state[i][j] != 0:
#                 distance += 1
#     return distance
#
#
# def h2(state, goal_state):
#     distance = 0
#     for i in range(3):
#         for j in range(3):
#             if state[i][j] != 0 and state[i][j] != goal_state[i][j]:
#                 goal_i, goal_j = -1, -1
#                 for x in range(3):
#                     for y in range(3):
#                         if goal_state[x][y] == state[i][j]:
#                             goal_i, goal_j = x, y
#                             break
#                 distance += abs(i - goal_i) + abs(j - goal_j)
#     return distance
#
#
# def Astar(start_state, goal_state, heuristic):
#     start_node = Node(start_state, None, 0, heuristic(start_state, goal_state))
#     open_list = [start_node]
#     heapq.heapify(open_list)
#     closed_set = set()
#     came_from = {}
#     expanded_nodes = 0
#
#     while open_list:
#         current_node = heapq.heappop(open_list)
#         expanded_nodes += 1
#
#         if current_node.state == goal_state:
#             path = []
#             while current_node:
#                 path.append(current_node.state)
#                 current_node = current_node.parent
#             path.reverse()
#             return path, expanded_nodes, len(open_list) + len(closed_set) - 1
#
#         closed_set.add(tuple(map(tuple, current_node.state)))
#         zero_i, zero_j = next((i, j) for i in range(3) for j in range(3) if current_node.state[i][j] == 0)
#         moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
#
#         for di, dj in moves:
#             new_i, new_j = zero_i + di, zero_j + dj
#             if 0 <= new_i < 3 and 0 <= new_j < 3:
#                 new_state = [row[:] for row in current_node.state]
#                 new_state[zero_i][zero_j], new_state[new_i][new_j] = new_state[new_i][new_j], new_state[zero_i][zero_j]
#                 new_state_tuple = tuple(map(tuple, new_state))
#
#                 if new_state_tuple in closed_set:
#                     continue
#
#                 new_node = Node(new_state, current_node, current_node.cost + 1, heuristic(new_state, goal_state))
#                 heapq.heappush(open_list, new_node)
#                 came_from[new_state_tuple] = current_node
#
#     return None, expanded_nodes, len(open_list) + len(closed_set) - 1
#
#
# # 初始状态和目标状态
# start_state = [[2, 8, 3], [1, 6, 4], [7, 0, 5]]
# goal_state = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
#
# # 使用不同的启发函数求解
# result_h1, expanded_nodes_h1, generated_nodes_h1 = astar(start_state, goal_state, h1)
# result_h2, expanded_nodes_h2, generated_nodes_h2 = astar(start_state, goal_state, h2)
#
# # 计算运行时间
# start_time_h1 = time.time()
# _, _, _ = Astar(start_state, goal_state, h1)
# run_time_h1 = time.time() - start_time_h1
# print(run_time_h1)
#
# start_time_h2 = time.time()
# _, _, _ = Astar(start_state, goal_state, h2)
# run_time_h2 = time.time() - start_time_h2
# print(run_time_h2)


# import numpy as np
#
#
# # 定义目标函数
# def objective_function(x):
#     return -x ** 2 + 4 * x - 3
#
#
# # 遗传算法参数
# POP_SIZE = 50  # 种群规模
# GENES = 10  # 基因长度（用于二进制编码）
# GENE_RANGE = (0, 10)  # 基因取值范围（解码后的实数范围）
# CROSSOVER_RATE = 0.8  # 交叉概率
# MUTATION_RATE = 0.01  # 变异概率
# NUM_GENERATIONS = 100  # 迭代次数
#
#
# # 初始化种群
# def initialize_population(pop_size, genes, gene_range):
#     population = np.random.rand(pop_size, genes)
#     population = population * (gene_range[1] - gene_range[0]) + gene_range[0]  # 将随机数映射到基因取值范围
#     return population
#
#
# # 解码函数（将二进制编码转换为实数）
# def decode(individual, gene_range):
#     # 这里我们实际上使用的是实数编码，所以解码函数就是直接返回
#     # 如果是二进制编码，这里需要进行转换，例如：
#     # decoded = sum(individual * (2 ** np.arange(len(individual))[::-1])) / (2 ** len(individual) - 1) * (gene_range[1] - gene_range[0]) + gene_range[0]
#     return individual[0]  # 我们只使用一个实数基因来表示解
#
#
# # 计算适应度
# def calculate_fitness(population, gene_range):
#     fitness = np.array([objective_function(decode(ind, gene_range)) for ind in population])
#     return fitness
#
#
# # 选择操作（轮盘赌选择）
# def selection(population, fitness):
#     total_fitness = np.sum(fitness)
#     probabilities = fitness / total_fitness
#     indices = np.random.choice(np.arange(len(population)), size=len(population), p=probabilities)
#     return population[indices]
#
#
# # 交叉操作（单点交叉，但这里我们简化为实数编码的算术交叉）
# def crossover(parent1, parent2, crossover_rate):
#     if np.random.rand() < crossover_rate:
#         alpha = np.random.rand()  # 交叉系数
#         child1 = alpha * parent1 + (1 - alpha) * parent2
#         child2 = alpha * parent2 + (1 - alpha) * parent1
#         return child1, child2
#     else:
#         return parent1, parent2
#
#
# # 变异操作（高斯变异）
# def mutate(individual, mutation_rate, gene_range):
#     if np.random.rand() < mutation_rate:
#         mutation_step = np.random.randn() * (gene_range[1] - gene_range[0]) / 10  # 变异步长
#         individual += mutation_step
#         # 确保个体在基因取值范围内
#         individual = np.clip(individual, gene_range[0], gene_range[1])
#     return individual
#
#
# # 遗传算法主函数
# def genetic_algorithm():
#     population = initialize_population(POP_SIZE, GENES, GENE_RANGE)
#     best_individual = None
#     best_fitness = float('-inf')
#
#     for generation in range(NUM_GENERATIONS):
#         fitness = calculate_fitness(population, GENE_RANGE)
#
#         # 更新最佳个体和适应度
#         max_fitness_idx = np.argmax(fitness)
#         if fitness[max_fitness_idx] > best_fitness:
#             best_fitness = fitness[max_fitness_idx]
#             best_individual = population[max_fitness_idx]
#
#         # 打印当前代最佳适应度和解
#         print(
#             f"Generation {generation + 1}, Best Fitness: {best_fitness}, Solution: {decode(best_individual, GENE_RANGE)}")
#
#         # 选择
#         population = selection(population, fitness)
#
#         # 交叉和变异
#         new_population = []
#         for i in range(0, POP_SIZE, 2):
#             parent1, parent2 = population[i], population[i + 1]
#             child1, child2 = crossover(parent1, parent2, CROSSOVER_RATE)
#             new_population.append(mutate(child1, MUTATION_RATE, GENE_RANGE))
#             new_population.append(mutate(child2, MUTATION_RATE, GENE_RANGE))
#
#         population = np.array(new_population)
#
#     return decode(best_individual, GENE_RANGE), best_fitness
#
#
# # 运行遗传算法
# best_solution, best_fitness = genetic_algorithm()
# print(f"Best Solution: {best_solution}, Best Fitness: {best_fitness}")